//给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否
//则返回 -1。 
//
// 示例 1: 
//
// 输入: nums = [-1,0,3,5,9,12], target = 9
//输出: 4
//解释: 9 出现在 nums 中并且下标为 4
// 
//
// 示例 2: 
//
// 输入: nums = [-1,0,3,5,9,12], target = 2
//输出: -1
//解释: 2 不存在 nums 中因此返回 -1
// 
//
// 
//
// 提示： 
//
// 
// 你可以假设 nums 中的所有元素是不重复的。 
// n 将在 [1, 10000]之间。 
// nums 的每个元素都将在 [-9999, 9999]之间。 
// 
//
// Related Topics 数组 二分查找 👍 1644 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    /**
     * 二分法，依旧是先排除一些特殊情况。
     * 实现左移右移。
     * 定义left、right，初始长度为0、length -1 ，
     * 循环，每次取中间值。如果需要右移，则left = left + i，如果需要左移，则right = right - i。
     * 跳出循环则返回 -1
     */

    public int search(int[] nums, int target) {
        int length = nums.length, right = length - 1, left = 0;
        if (length == 0 || nums[length - 1] < target || nums[0] > target) {
            return -1;
        }
        if (length == 1 && nums[length - 1] == target) {
            return 0;
        }
        // 二分查找
        while(left <= right) {
            int i = (right + left) / 2 ;
            int num = nums[i];
            if (num == target) {
                return i;
            }
            // zuo移
            if (num > target) {
                right = i - 1;
                continue;
            }
            if (num < target) {
                left = i + 1;
            }
        }
        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
